import java.util.Arrays;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/19 8:48
 * @description:
 */
public class Solution611 {
    /**
     * 因此，我们可以将数组 nums 进行升序排序，随后使用二重循环枚举 a 和 b。设 a=nums[i],b=nums[j]，为了防止重复统计答案，
     * 我们需要保证 i < j。剩余的边 c 需要满足 c < nums[i]+nums[j]，我们可以在 [j+1,n−1] 的下标范围内使用二分查找（其中 n 是数组 nums 的长度），
     * 找出最大的满足 nums[k]< nums[i]+nums[j] 的下标 k，这样一来，在 [j+1,k] 范围内的下标都可以作为边 c 的下标，我们将该范围的长度 k−j 累加入答案。
     * <p>
     * 当枚举完成后，我们返回累加的答案即可。
     * <p>
     * 细节
     * <p>
     * 注意到题目描述中 nums 包含的元素为非负整数，即除了正整数以外，nums 还会包含 0。
     * 但如果我们将 nums 进行升序排序，那么在枚举 a 和 b 时出现了 0，那么 nums[i] 一定为 0。
     * 此时，边 c 需要满足 c < nums[i]+nums[j]=nums[j]，而下标在 [j+1,n−1] 范围内的元素一定都是大于等于 nums[j] 的，因此二分查找会失败。
     * 若二分查找失败，我们可以令 k=j，此时对应的范围长度 k−j=0，我们也就保证了答案的正确性。
     *
     * @param nums
     * @return
     */
    public int triangleNumber(int[] nums) {
        int res = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int a = nums[i], b = nums[j];
                int k = binarySearch(nums, j + 1, nums.length - 1, a + b);
                if (k != -1) {
                    res += (k - j);
                }
            }
        }
        return res;
    }

    public int binarySearch(int[] nums, int low, int high, int target) {
        int left = low, right = high;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 循环终止后：left 是第一个 >= target 的索引，left-1 是最后一个 < target 的索引
        if (left - 1 >= 0) { // 存在小于 target 的元素
            return left - 1; // 返回该元素的索引
        } else { // 所有元素都 >= target，无符合条件的元素
            return -1; // 用 -1 表示不存在（可根据需求调整）
        }
    }

    /**
     * 我们将当 a=nums[i],b=nums[j] 时，最大的满足 nums[k] < nums[i]+nums[j] 的下标 k 记为 k
     * i,j
     * ​
     * 。可以发现，如果我们固定 i，那么随着 j 的递增，不等式右侧 nums[i]+nums[j] 也是递增的，因此 k
     * i,j
     * ​
     * 也是递增的。
     * <p>
     * 这样一来，我们就可以将 j 和 k 看成两个同向（递增）移动的指针，将方法一进行如下的优化：
     * <p>
     * 我们使用一重循环枚举 i。当 i 固定时，我们使用双指针同时维护 j 和 k，它们的初始值均为 i；
     * <p>
     * 我们每一次将 j 向右移动一个位置，即 j←j+1，并尝试不断向右移动 k，使得 k 是最大的满足 nums[k] < nums[i]+nums[j] 的下标。我们将 max(k−j,0) 累加入答案。
     * <p>
     * 当枚举完成后，我们返回累加的答案即可。
     * <p>
     * 细节
     * <p>
     * 与方法一中「二分查找的失败」类似，方法二的双指针中，也会出现不存在满足 nums[k] < nums[i]+nums[j] 的下标的情况。此时，指针 k 不会出现在指针 j 的右侧，即 k−j≤0，因此我们需要将 k−j 与 0 中的较大值累加入答案，防止错误的负数出现。
     *
     * @param args
     */
    public int triangleNumber2(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int k = i;
            for (int j = i + 1; j < n; ++j) {
                while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
                    ++k;
                }
                ans += Math.max(k - j, 0);
            }
        }
        return ans;
    }

    public int triangleNumber3(int[] nums) {
        int sum = 0;
        Arrays.sort(nums);
        int end = nums.length - 1;
        for (; end > 1; end--) {
            int right = end - 1;
            int left = 0;
            while (left < right) {
                if (nums[left] + nums[right] <= nums[end]) {
                    left++;
                } else {
                    sum += right - left;
                    right--;
                }
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution611 solution = new Solution611();
        System.out.println(solution.triangleNumber(new int[]{2, 2, 3, 4}));
        System.out.println(solution.triangleNumber(new int[]{4, 2, 3, 4}));
    }
}
